package com.leetcode.www;

import java.util.HashSet;
import java.util.Set;

/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n
 * User:yxd
 * Date:2022-04-11
 * Time:13:06
 */
public class Everyday357 {
    public int countNumbersWithUniqueDigits1(int n) {//但是这样的做法时间复杂度较高
        int count = 0;
        for(int i = 0;i < Math.pow(10,n);i ++){
            if(isT(i)){
                count ++;
            }
        }
        return count;
    }
    public boolean isT(int x){
        Set<Integer> set = new HashSet<>();
        while(x != 0){
            int a = x % 10;
            if(!set.contains(a)){//看有无重复的元素
                set.add(a);
            }else{
                return false;
            }
            x /= 10;
        }
        return true;
    }
    public int countNumbersWithUniqueDigits(int n) {//可以按照排列组合的方式,统计每个位数上数字不同的全部个数
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 10;
        }
        int count = 10, x = 9;
        for (int i = 0; i < n - 1; i++) {
            x *= 9 - i;//第一位数字有1~9九种选择,第二位数字有0~9减去第一位数字选去的也是九位,然后后面的依次减1就可以
            count += x;
        }
        return count;
    }
}
